package leetcode.editor.cn.dsa20_heap;
//设计一个找到数据流中第 k 大元素的类（class）。注意是排序后的第 k 大元素，不是第 k 个不同的元素。
//
// 请实现 KthLargest 类： 
// KthLargest(int k, int[] nums) 使用整数 k 和整数流 nums 初始化对象。
// int add(int val) 返回当前数据流中第 k 大的元素。 
//
// 示例： 
//输入：
//["KthLargest", "add", "add", "add", "add", "add"]
//[[3, [4, 5, 8, 2]], [3], [5], [10], [9], [4]]
//输出：
//[null, 4, 5, 5, 8, 8]
//
//解释：
//KthLargest kthLargest = new KthLargest(3, [4, 5, 8, 2]);
//kthLargest.add(3);   // return 4
//kthLargest.add(5);   // return 5
//kthLargest.add(10);  // return 5
//kthLargest.add(9);   // return 8
//kthLargest.add(4);   // return 8
// 
//提示：
// 1 <= k <= 104
// 0 <= nums.length <= 104 
// -104 <= nums[i] <= 104 
// -104 <= val <= 104 
// 最多调用 add 方法 104 次 
// 题目数据保证，在查找第 k 大元素时，数组中至少有 k 个元素 
// 
// Related Topics 堆 设计 
// 👍 175 👎 0

import java.util.PriorityQueue;

public class KthLargestElementInAStream703 {
    public static void main(String[] args) {
        int[] nums = {4, 5, 8, 2};
        KthLargest kthLargest = new KthLargestElementInAStream703().new KthLargest(3, nums);
        System.out.println(kthLargest.add(3)); //4
        System.out.println(kthLargest.add(5)); //5
        System.out.println(kthLargest.add(10)); //5
        System.out.println(kthLargest.add(9)); //8
        System.out.println(kthLargest.add(4)); //8
    }

    //leetcode submit region begin(Prohibit modification and deletion)
    class KthLargest {
        /**
         * 解题思路：
         * 创建一个大小为k的小顶堆，这个小顶堆存放前k大的数据。那么自然堆顶元素就刚好是第k大的元素
         * 添加元素时，当加入的元素比堆顶元素大，则让堆顶出队，让当前元素入队
         */
        PriorityQueue<Integer> queue;
        int k;
        public KthLargest(int k, int[] nums) {
            this.k = k;
            // 创建一个容量为k的小顶堆
            queue = new PriorityQueue<>(k);
            for (int i = 0; i < nums.length; i++) {
                // 堆未满或者当前元素比堆顶元素大，进行入队
                if (queue.size() != k || nums[i] > queue.peek()) {
                    if (queue.size() == k) queue.poll(); // 删除堆顶元素
                    queue.offer(nums[i]); // 元素入队
                }
            }
        }

        public int add(int val) {
            // 堆未满或者当前元素比堆顶元素大，进行入队
            if (queue.size() != k || val > queue.peek()) {
                if (queue.size() == k) queue.poll(); // 删除堆顶元素
                queue.offer(val); // 元素入队
            }
            return queue.peek();
        }
    }

    /**
     * Your KthLargest object will be instantiated and called as such:
     * KthLargest obj = new KthLargest(k, nums);
     * int param_1 = obj.add(val);
     */
    //leetcode submit region end(Prohibit modification and deletion)
}